package com.wlj.utils.suanfa;

import java.util.*;

public class Solution {

    //第一题
    public static int[][] merge(int[][] intervals){
        if (intervals==null){
            return null;
        }
        if(intervals.length<=1){
            return intervals;
        }
        List<int[]> res = new ArrayList<>();
        //先只考虑第一个区间，它相当于一个合并后的区间
        //初始化合并后的区间开始位置
        int s=intervals[0][0];
        //初始化合并后的区间结束位置
        int e=intervals[0][1];
        int length = intervals.length;
        for (int i = 0; i < length; i++) {
            //若当前遍历到的区间start小于合并后的区间end，说明当前区间和合并后的区间存在重合
            if(intervals[i][0]<=e){
                //设置e为较大的值，此时[s,e]为目前合并后的区间
                e=Math.max(e,intervals[i][1]);
            }else{
                //若当前遍历到的区间start大于之前合并后的区间end，说明当前区间和合并后的区间不重合，则之前合并后的区间已无法再合并，可加入res
                res.add(new int[]{s,e});
                //重置 s,e 为当前遍历的区间的start end
                s=intervals[i][0];
                e=intervals[i][1];
            }
        }
        res.add(new int[]{s,e});
        int[][] resArr=new int[res.size()][];
        for (int i = 0; i < resArr.length; i++) {
            resArr[i]=res.get(i);
        }
        return resArr;
    }


    //第二题
    public static boolean valid(String word,String abbr){
        if(abbr==null||abbr.length()==0){
            return false;
        }
        char[] wordChars = word.toCharArray();
        Stack<String> wordStack = new Stack<>();
        for (int i = 0; i < wordChars.length; i++) {
            wordStack.push(wordChars[i]+"");
        }
        char[] abbrChars = abbr.toCharArray();
        Stack<String> abbrStack = new Stack<>();
        for (int i = 0; i < abbrChars.length; i++) {
            abbrStack.push(abbrChars[i]+"");
        }
        String temp="";
        while (!abbrStack.empty()){
            if(wordStack.empty()){
                return false;
            }
            String atop = abbrStack.pop();
            if(isLetter(atop.charAt(0))){
                if(temp.length()>0){
                    int c = Integer.parseInt(temp);
                    for (int i = 0; i < c; i++) {
                        if(wordStack.empty()){
                            return false;
                        }
                        wordStack.pop();
                    }
                    temp="";
                }
                String wtop = wordStack.pop();
                if(!atop.equals(wtop)){
                    return false;
                }
            }else{
                temp=atop+temp;
            }
        }
        if(wordStack.empty()){
            return true;
        }else{
            return false;
        }
    }


    private static boolean isLetter(char a){
        return 97<=a&&a<=122;
    }




    //第三题
    public static int minPath(int n, int[][] edges, int start, int end){
        //虽然求的是所有惩罚值的"或"运算的值，其实还是一个求最短路径的问题，因为题目条件:无负权边 ，因此
        //可用dijkstra算法求最短路径
        //根据题目所给条件 1<=n<=1000   1<=edges.length<=10000
        //有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图，那么可用邻接表来表示
        /**
         * 左边一列为图的顶点，右边为与它相邻的顶点
         * 0 1
         * 1 0 2 3
         * 2 1 3
         * 3 1 2
         */
        int[] distTo=new int[n+1];    //存储源点到各点的距离
        boolean[] marked=new boolean[n+1];  //表示该顶点是否标记过，原点到该点的最短路径已找到则标记该点
        ArrayList<Edge> from=new ArrayList<Edge>(); //存储指向该顶点的边Edge，求最短路径使用
        for(int i=1;i<=n;i++){
            distTo[i]=0;
            marked[i]=false;
            from.add(null);
        }
        SparseGraph sg=initGraph(n,edges);
        IndexMinHeap imh=new IndexMinHeap(sg.V());
        marked[start]=true;
        imh.insert(start, distTo[start]);
        //Dijkstra
        while(!imh.isEmpty()){
            //找出
            int v=imh.extractMinIndex();
            marked[v]=true;
            ArrayList<Edge> arr=sg.getSideEdges(v);
            Iterator<Edge> ite=arr.iterator();
            while(ite.hasNext()){
                Edge e=ite.next();
                int w=e.other(v);
                if(!marked[w]){     //w没有marked即表示s到w的最短路径没有找到
                    if(from.get(w-1)==null){  //from.get(w)==null表示e这条路径没访问过
                        distTo[w]=distTo[v]+e.wt();
                        from.set(w-1, e);
                        if(!imh.contain(w))
                            imh.insert(w, distTo[w]);
                    }else{ //from.get(w)!=null表示e这条路径访问过，尝试使用"松弛操作"，若经由v点折回w点的距离小于distTo[w]则更新distTo[w]
                        if(distTo[v]+e.wt()<distTo[w]){
                            distTo[w]=distTo[v]+e.wt();
                            from.set(w-1, e);
                            if(imh.contain(w))
                                imh.set(w, distTo[w]);
                        }
                    }

                }
            }
        }
        //源点到w点是否有路径
        if(!marked[end]){
            return -1;
        }
        ArrayList<Edge> path=new ArrayList<>();
        Stack<Edge> s = new Stack<Edge>();
        Edge e=from.get(end-1);      //得到指向w点的路径
        int x=end;
        while(e!=null){
            s.push(e);
            int i = e.other(x) - 1;
            e=from.get(i);
            x=i+1;
        }
        while(!s.isEmpty()){
            e=s.peek();
            path.add(e);
            s.pop();
        }
        for(int i=0;i<path.size();i++){
            System.out.print(path.get(i).v()+"->");
            if(i==path.size()-1){
                System.out.print(path.get(i).w());
            }
        }
        int res=0;
        for (Edge edge : path) {
            res=(res|edge.wt());
        }
        System.out.println();
        return res;
    }

    private static SparseGraph initGraph(int n, int[][] edges){
        SparseGraph sg=new SparseGraph(n,edges);
        for(int i=0;i<edges.length;i++){
            sg.addEdge(edges[i][0], edges[i][1],edges[i][2]);
        }
        for(int i=1;i<=n;i++){
            System.out.print(i+" :");
            ArrayList<Edge> srr=sg.getSideEdges(i);
            Iterator<Edge> ite=srr.iterator();
            while(ite.hasNext())
                System.out.print(ite.next().other(i)+" ");
            System.out.println();
        }
        return sg;
    }
}
